package zuochengyun.chapter8;

//数组中未出现的最小正整数
public class MissMinimumPositive {

	//感觉该算法虽然巧妙，但是很难摸透
	//给定无序整形数组，求未出现的最小正整数
	public int missNum(int[] arr){
		//left表示遍历到目前为止，数组arr已经包含的正整数范围是[1, left]
		int left = 0;
		//right表示在后续最优情况下，arr可能包含的正整数范围是[1, right]
		//初始令right = N，表示最好为包括[1...N]
		int right = arr.length;
		while(left <= right){
			//如果arr[left] = left + 1,说明是连续的
			if(arr[left] == left + 1){
				left++;
			}else if(arr[left] <= left || arr[left] > right || arr[arr[left] - 1] == arr[left]){
				//在没有遍历arr[left]之前，后续最优为[left + 1, right],而此时出现了arr[left] <= left
				//说明[left + 1, right]范围的数少了一个，变为[1, right - 1]
				//将arr最后位置的数(right - 1)放置位置left上，令right--
				
				//同理。arr[left] > right,也说明后续最优变为[1, right - 1]
				
				//如果arr[left] 在[left + 1, right]范围上，那么这个数应该放在arr[left] - 1的位置上
				//如果arr[arr[left] - 1] == arr[left]；那么说明一个数字重复了两次，那么同样会使范围减1
				arr[left] = arr[--right];
			}else{
				//如果没有执行上述代码，说明找到了[left + 1, right]范围上的数，并且没有重复
				//就将arr[left]放置arr[left] - 1的位置上
				swap(arr, left, arr[left] - 1);
			}
		}
		//最后left与right位置碰在一起，说明已经找到的范围为[1...right]，此时返回right(= left) + 1
		return left + 1;
	}

	private void swap(int[] arr, int left, int i) {
		int temp = arr[left];
		arr[left] = arr[i];
		arr[i] = temp;
	}
}
